package day05;

// 练习day05
// 寻找重复数
// 使用环形链表的方法

public class Main2 {
    public int findDuplicate(int[] nums) {
        // 使用快慢指针，直到相等时就退出循环
        int slow = 0;
        int fast = 0;
        while(true) {
            slow = nums[slow]; // 一步
            fast = nums[nums[fast]]; // 两步
            if(fast == slow) {
                break; // 退出循环
            }
        }
        // 定义第三个指针finder，用来找环形链表的入口！！
        int finder = 0;
        // 一直循环，直到与slow相遇（同时走）
        while(true) {
            finder = nums[finder];
            slow = nums[slow];
            if(finder == slow) {
                break;
            }
        }
        // 此时就是环形的入口
        return finder;
    }
}
